1353E - K-periodic Garland - CodeForces Solution

brute force dp greedy *1900

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    ans = []
    for i in range(k):
        c = t = 0
        for j in range(i, n, k):
            if s[j] == '1':
                c += 1
            else:
                c -= 1
            t = min(t, c)
            ans += c - t,
    print(s.count('1') - max(ans))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;

        cin >> n >> k;

        string s;

        cin >> s;

        // int pre[n];
        vector<int> pre(n, 0);
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                pre[i] = s[i] - '0';
            else
                pre[i] += pre[i - 1] + (s[i] - '0');
        }

        vector<int> sum(n, 0);
        for (int i = n - 1; i >= 0; i--)
        {
            int xr = (s[i] - '0') ^ 1;
            if (i + k - 1 < n)
            {
                xr += pre[i + k - 1] - pre[i];
            }
            else
            {
                xr += pre[n - 1] - pre[i];
            }
            if (i + k < n)
            {
                xr += sum[i + k];
            }
            int r = pre[n - 1] - pre[i] + (s[i] - '0');
            sum[i] = min(r, xr);
        }
        int cnt = 1e15;
        for (int i = 0; i < n; i++)
        {
            int s = sum[i];
            if (i)
                s += pre[i - 1];

            cnt = min(cnt, s);
        }
        cout << cnt << endl;
    }
    // int i = 0, j = n - 1;
    // while (i < n && s[i] == '0')
    //     i++;
    // while (j >= 0 && s[j] == '0')
    //     j--;
    // if (j < i)
    // {
    //     cout << "0" << endl;
    //     continue;
    // }
    // int total = 0;
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         total++;
    //     }
    // }
    // vector<int> rem(k + 1, 0);
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         rem[(l - i) % (k)]++;
    //     }
    // }
    // int ans = 1e6;
    // cout << total << endl;
    // cout << (j - i + 1) / k << endl;

    // for (int l = 0; l < k; l++)
    // {
    //     cout << rem[l] << " ";
    //     ans = min(ans, (j - i + 1) / k - rem[l] + total - rem[l]);
    //     cout << ans << " ";
    // }
    // cout << ans << endl;
}


Comments

Submit
0 Comments
More Questions

779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number
279. Perfect Squares
275. H-Index II
274. H-Index
260. Single Number III
240. Search a 2D Matrix II
238. Product of Array Except Self
229. Majority Element II